#定义节点类
class LNode:
    def __init__(self,elem,next_ = None):
        self.elem = elem
        self.next = next_

#定义异常
class LinkedListUnderflow(ValueError):
    pass

#定义链表类
class LList:
    def __init__(self) -> None:     #初始为空表
        self._head = None
        self._rear = None
        self._num = 0
    def is_empty(self):             #判断是否为空表
        return self._head is None
    def prepend(self,elem):         #表前加节点
        self._head = LNode(elem,self._head)
        self._rear.next = self._head
        self._num += 1
    def pop(self):                  #删除第一个节点并返回节点内容，链表为空时抛出异常
        if self._head is None:
            raise LinkedListUnderflow("in pop")
        e = self._head.elem
        self._head = self._head.next
        self._rear.next = self._head
        self._num -= 1
        return e

    def append(self,elem):          #链表后端添加节点
        if self._head is None:
            self._head = LNode(elem)
            self._rear = self._head
            self._num += 1
            return
        self._rear.next = LNode(elem,self._head)
        self._rear = self._rear.next
        self._num += 1
    
    def pop_last(self):
        if self._head is None:#空表
            raise LinkedListUnderflow("in pop_last")
        p = self._head
        if p.next is None:
            e = p.elem
            self._head = None
            self._num -= 1
            return e
        while p.next != self._rear:
            p = p.next
        e = p.next.elem
        self._rear = p
        self._num -= 1
        return e

    def printall(self):
        p = self._head
        while p != self._rear:
            print (p.elem,end='')
            if p.next is not None:
                print(',',end='')
            p = p.next
        print(p.elem)
    def is_in(self,elem):
        p = self._head
        for i in range(self._num):
            if elem == p.elem:
                return p
            p = p.next
        return False
    def is_between(self,i,j,num):
        p = self.is_in(i).next
        t = 0
        while t < self._num:
            if p.elem == num or p.elem == j:
                return p.elem == num
            p = p.next
            t += 1
        return False
        
        
    def element(self):
        p = self._head
        while p != self._rear:
            yield p.elem
            p = p.next
        yield p.elem




    
